The present invention relates generally to design verification in transition systems and to reachability analysis in finite state machines, and specifically to hardware and software verification of integrated circuit design using methods of reachability analysis.
Hardware verification is currently the bottleneck and the most expensive task in the design of a semiconductor integrated circuit. Model checking is a method of formal verification that is gaining in popularity for this purpose. The method is described generally by Clarke et al., in Model Checking (MIT Press, 1999), which is incorporated herein by reference.
To perform model checking of the design of a device, a verification engineer reads the definition and functional specifications of the device and then, based on this information, writes a set of properties (also known as a specification) that the design is expected to fulfill. The properties are written in a suitable specification language for expressing temporal logic relationships between the inputs and outputs of the device. A hardware model (also known as an implementation) of the design, which is typically written in a hardware description language, such as VHDL or Verilog, is then tested to ascertain that the model satisfies all of the properties in the set under all possible input sequences. Such testing is a form of reachability analysis, in that it verifies that beginning from an initial state, the device as designed will, under appropriate conditions, reach an intended final state. Additionally, the testing verifies that particular xe2x80x9cbadxe2x80x9d states will not be reached from an initial state of the device under any conditions.
Model checking is preferably carried out automatically by a symbolic model checking program, such as SMV, as described, for example, by McMillan in Symbolic Model Checking (Kluwer Academic Publishers, 1993), which is incorporated herein by reference. A number of practical model checking tools are available, among them RuleBase, developed by IBM, which is described by Beer et al. in xe2x80x9cRuleBase: an Industry-Oriented Formal Verification Tool,xe2x80x9d in Proceedings of the Design Automation Conference DAC""96 (Las Vegas, Nev., 1996), which is incorporated herein by reference.
Even if the verification engineer is able to detect the existence of a design defect, there is an additional need to construct a sequence of states and transitions (a path) that leads to the problematic state of the design. This path is called a counterexample. Having such a counterexample allows the engineer to assess the impact of the problem and to address the bug specifically during redesign. Recent research described by Aziz and Ganai in xe2x80x9cEfficient Coverage Directed State Space Search,xe2x80x9d in Proceedings of the International Workshop on Logic Synthesis (Lake Tahoe, Calif., 1998), and by Dill and Yand in xe2x80x9cValidation with Guided Search of the State Space,xe2x80x9d in Proceedings of the 35th ACM/IEEE Design Automation Conference (1998), have noted the importance of this constructive counterexample approach. Both of these articles are incorporated herein by reference.
The most commonly used method in industry of finding a counterexample is to do a type of breadth-first search (BFS) of all states reached from a starting state and see if a problem state is reached. Because BFS is an exhaustive search, it explores all possible transition paths between states. Often, however, some of the paths may be ruled out as potential counterexamples by simple methods. Also, BFS may not detect even a very simple counterexample until it has investigated many other paths. Thus, BFS may spend significantly more time and computational resources than are tolerable to the engineer in arriving at a solution.
Another approach has been to use a directed search, as described by Dill and Yand, cited earlier, and by Abraham et al., in xe2x80x9cOn Combining Formal and Informal Verification,xe2x80x9d in Proceedings of the Computer Aided Verification Conference (1997), which is incorporated herein by reference. In a directed search, a heuristic is used to assign scores to states. The scores are meant to represent the likelihood that the state is a member of a counterexample path. By ranking the states by their scores, the search is directed toward those states believed most likely to produce a counterexample.
The efficiency and efficacy of a directed search are highly dependent on the scoring heuristic employed. Methods of directed search known in the art use heuristics that are either chosen a priori by the user or are determined by pre-processing the model immediately prior to beginning the search. Choosing a good heuristic in advance is very difficult. Pre-processing to find a good heuristic can be extremely time consuming.
If a heuristic does not lead to the production of a counterexample when one is known to exist, the heuristic scores must be refined. One approach has been to refine the entire model, as described by Clarke et al., in xe2x80x9cCounterexample-Guided Abstraction Refinement,xe2x80x9d in Proceedings of the Computer Aided Verification Conference (2000), which is incorporated herein by reference.
Any implementation of these approaches relies on an underlying data structure that can represent Boolean functions efficiently. This efficiency is measured by the amount of memory space required by the data structure to represent the function and by the time and complexity required to manipulate the data structures. The data structure of choice used by practitioners in the art has been the binary decision diagram (BDD). In particular, many of the approaches to finding counterexamples mentioned above use implicitly conjoined BDDs, as described by Dill and Hu in xe2x80x9cEfficient Verification with BDDs using Implicitly Conjoined Invariants,xe2x80x9d in Lecture Notes in Computer Science 697 (Springer-Verlag, 1993), which is incorporated herein by reference. Some methods of manipulating BDDs are described by Ravi et al., in xe2x80x9cApproximation and Decomposition of Binary Decision Diagrams,xe2x80x9d in Proceedings of the 35th ACM/IEEE Design Automation Conference (1998), by Ravi and Somenzi, in xe2x80x9cHigh-Density Reachability Analysis,xe2x80x9d in Proceedings of the IEEE International Conference on Computer Aided Design (1994), and by Beer and Geist in xe2x80x9cEfficient Model Checking by Automated Ordering of Transition Relation Partitions,xe2x80x9d in Proceedings of the Computer Aided Verification Conference (1994), which are incorporated herein by reference.
Preferred embodiments of the present invention provide an improved method for finding counterexamples in a transition system. The method is particularly useful in formal verification of hardware and software designs. A heuristic is constructed xe2x80x9con the flyxe2x80x9d for use in choosing states of the system that are likely candidates to belong to counterexamples. When the current heuristic is discovered to be incorrect, it is refined based on knowledge of earlier mistakes. As a result, the process of refinement is efficient and low in overhead. When the correct heuristic is discovered, it identifies a small portion of the state space of the system in which it is known that a counterexample can be found. This portion of the state space can be searched quickly to find the counterexample.
In preferred embodiments of the present invention, a formal verification framework receives as part of its input a design model having the form of a transition system. The system comprises a set of states, including a subset of initial states and a subset of final states, along with a transition relation between the states. An operator of the system identifies a set of xe2x80x9cbadxe2x80x9d states, which should not be reachable from an initial state of the system if the model is correct.
The framework works in two directions to find a heuristic that will lead to a counterexample, i.e., a path from an initial state to a bad state. The system searches backwards from the bad states toward the initial states by estimating the minimum number of transition steps needed to reach a bad state from different points in the state space. The system searches forward from the initial states to find states that are reachable from the initial state by exploring those states previously known to be reachable and which have been estimated to be closest to the bad states. If the exploration does not find an overlap between the states found in the backward and forward searches, the estimate is refined for the relevant states. The process terminates when a bad state is found to be reachable from an initial state. At this point, the system finds a path from an initial state to a bad state by performing a breadth first search on the set of reachable states. This path is identified as a counterexample.
Thus, preferred embodiments of the present invention enable counterexamples to be identified efficiently by reducing the scope of the search that must be conducted, by estimating those states of the model more likely to be included in a counterexample, and by refining those estimates upon discovering their inaccuracy. Since only a small, relevant portion of the model is refined, preferred embodiments of the present invention are generally more efficient than methods known in the art, such as the method described in the above-mentioned article by Clarke et al., in which the entire model is refined. The present invention is broadly applicable, with minimal user involvement and, typically, requires significantly less time to run than methods previously known in the art.
In some preferred embodiments of the present invention, when working backward from the bad states, an intermediate state encountered is placed in a set representing the minimum number of transition steps needed to reach a bad state from the intermediate state. The system maintains lists Di initially comprising all states estimated to be i steps from a bad state. D0 is thus a list of the bad states. A state""s score is the lowest i such that Di contains the state. Preferred embodiments of the current invention do not explicitly maintain the states"" scores, however.
The framework also builds and maintains a list of states it knows to be reachable from an initial state by choosing known reachable states that have low scores (referred to as candidates) and computing those states"" successors according to the transition relation. The successors are added to the list of reachable states. This process is repeated until either a bad state is reached or until none of the computed successors have a lower score than any of the candidates (more specifically, until no candidate from Di has a successor in Dixe2x88x921). In the latter case, the framework heuristically refines its distance estimate for relevant intermediate states and adjusts Di accordingly. This may result in increasing the scores of some of the intermediate states. The framework then resumes the forward search process.
Preferably, when performing the forward search and finding that no candidate in Di has a successor in Dixe2x88x921, the framework refines its distance estimates for relevant states by repeatedly approximating Di with increasing exactness until the approximation no longer contains any of the candidates, and finding a new candidate from Di that does have a successor in Dixe2x88x921. It then resumes the forward search process by looking at Dixe2x88x921 to find a state with a successor in Dixe2x88x922, and so on. This process of repeated local estimation enables the verification system to construct counterexamples with enhanced efficiency by comparison with formal verification systems known in the art.
Preferred embodiments of the present invention use implicitly conjoined binary decision diagrams to represent sets of states, wherein each list Di is represented by implicitly conjoined binary decision diagrams.
Although preferred embodiments described herein are directed to methods for hardware verification, the principles of the present invention are similarly applicable to other areas of system analysis requiring reachability analysis, particularly systems represented as finite state machines and other transition systems.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for finding a counterexample on a system of states, including one or more initial states and one or more bad states, and a transition relation among the states, including:
assembling a first set of the states known to be reachable from the initial states in accordance with the transition relation;
defining a second set of the states from which it is estimated that one of the bad states is reachable in accordance with the transition relation;
modifying the sets of the states until a definition of the second set is found such that from one or more of the states in an intersection of the first and second sets, there is at least one of the bad states that can be reached in a given number of steps of the transition relation; and
searching for the counterexample over the states in the intersection.
Preferably, modifying the sets of the states includes iteratively modifying the first and second sets until the intersection is found. Further preferably, defining the second set of the states includes defining n+1 sets of the states, referred to as D0 through Dn, wherein D0 includes the bad states, such that for each value of an index i, which assumes values from 1 to n, it is estimated that one of the bad states can be reached in i steps of the transition relation from at least one of the states in Di, and wherein modifying the second set includes:
(a) choosing as candidates a subset of the states from the intersection of Di and the first set;
(b) verifying that at least one of the candidates can reach one of the states in Dixe2x88x921 in one step of the transition relation;
(c) refining the estimate of Di when none of the candidates can reach in one step any of the states in Dixe2x88x921; and
(d) repeating steps (a) through (c) until one of the candidates is verified to reach one of the states in Dixe2x88x921 in one step of the transition relation.
Most preferably, modifying the second set includes decrementing i, beginning from an initial value of n, and repeating steps (a) through (d) until one of the candidates is verified to reach one of the bad states in one step of the transition relation.
Preferably, searching for the counterexample includes performing a search over the first set of states, most preferably a breadth first search over the first set of states.
In a preferred embodiment, step (c) includes:
(e) producing a set Dxe2x80x2ixe2x88x921 as a superset of Dixe2x88x921 which has a small representation size in a data structure used to represent the states;
(f) computing a set Axe2x80x2 to approximate a set of the states from which the states in Dxe2x80x2ixe2x88x921 can be reached in one step of the transition relation;
(g) increasing a precision of the approximation for Axe2x80x2 until Axe2x80x2 does not contain any of the candidates;
(h) producing a set A as a superset of Axe2x80x2 that has a small representation size in the data structure but does not contain any of the candidates; and
(i) computing the modified estimate of Di as the intersection of a previous estimate of Di and A.
Preferably, the data structure includes a binary decision diagram (BDD).
Additionally or alternatively, choosing the candidates includes finding a first state in the intersection of Di and the first set, and adding to the candidates further states from the intersection which are found to have a large measure of difference relative to the first state.
Preferably, assembling the first set of the states and defining the second set of the states include representing the states as implicitly conjoined binary decision diagrams (BDDs) of boolean variables that define the states.
In a preferred embodiment, the system includes a model of an electronic device, and the states represent states assumed by the device in operation, and the counterexample is indicative of a deviation of the model from a specification of the device.
In another preferred embodiment, the transition relation includes a transition function, and the system includes a finite state machine.
There is also provided, in accordance with a preferred embodiment of the present invention, apparatus for finding a counterexample on a system of states, including one or more initial states and one or more bad states, and a transition relation among the states, the apparatus including a verification processor arranged to assemble a first set of the states known to be reachable from the initial states in accordance with the transition relation, to define a second set of the states from which it is estimated that one of the bad states is reachable in accordance with the transition relation, to modify the sets of the states until a definition of the second set is found such that from one or more of the states in an intersection of the first and second sets, there is at least one of the bad states that can be reached in a given number of steps of the transition relation, and to search for the counterexample over the states in the intersection.
There is further provided, in accordance with a preferred embodiment of the present invention, a computer software product for finding a counterexample on a system of states, including one or more initial states and one or more bad states, and a transition relation among the states, the product including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to assemble a first set of the states known to be reachable from the initial states in accordance with the transition relation, to define a second set of the states from which it is estimated that one of the bad states is reachable in accordance with the transition relation, to modify the sets of the states until a definition of the second set is found such that from one or more of the states in an intersection of the first and second sets, there is at least one of the bad states that can be reached in a given number of steps of the transition relation, and to search for the counterexample over the states in the intersection.